#!/usr/bin/env python
#-*- coding: utf-8 -*-

import sys
import time
import math

'''

 autor: António Delgado
 Data: 11-03-2013


'''
class Mergesort:
    def __init__(self, A):
        self.A = A
        
    def Merge(self, A, p, q, r):
        n1 = q - p + 1
        n2 = r - q
    
        L = [0 for k in range (n1+1)]
        R = [0 for k in range (n2+1)]
    
        for i in range(n1):
            L[i] = self.A[p + i]
            pass
        for j in range(n2):
            R[j] = self.A[q + j + 1]
            pass
        
    
        L[n1] = R[n2] = sys.maxint

        i = 0
        j = 0
    
        for k in range(p, r + 1):
            if L[i] <= R[j]:
                self.A[k] = L[i]
                i = i + 1
            else:
                self.A[k] = R[j]
                j = j + 1
                
    def Mergesort(self, A, p, r):
        if p < r:
            q = int(math.floor((p + r) / 2))
            self.Mergesort(self.A, p, q)
            self.Mergesort(self.A, q + 1, r)
            self.Merge(self.A, p, q, r)
        return self.A

A = [2 ,3 ,4 ,1 ,6 ,7 ,8 ,1 , 2 , 4 , 5 , 7 , 1 , 2 , 3 , 6 , 7 ,8]

execucaoOne= time.clock()
print 'Desordenado:', A
M = Mergesort(A)
execucaoTwo= time.clock()
print 'Ordenado:', M.Mergesort(A, 0, len(A) - 1)
print 'Time Inicial:', execucaoOne
print 'Time final:', execucaoTwo
print 'Time Final-Inicial:', execucaoTwo-execucaoOne

from random import uniform
from time import clock

Z = [1] + range(50, 1050, 50)
T = []
M = 25
for n in Z:
    A = [ uniform(0.0,1.0) for k in xrange(n)]
    tempos = []
    for k in range(M):
        t1 = clock()
        Mergesort(A)
        t2 = clock()
        tempos.append(t2-t1)
    media = reduce(lambda x, y: x + y, tempos) / len(tempos)
    var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
    
    T.append((n,media, var))

X = [n for n, media, var in T]
Y = [media for n, media, var in T]
ct=15e6
Z = [n * math.log(n)/ct for n, media, var in T]

import matplotlib.pyplot as plt
plt.grid(True)
plt.ylabel(u'T(n) - tempo de execução médio em segundos')
plt.xlabel(u'n - número de elementos')
plt.plot(X,Y,'rs', label="resultado experimental")
plt.plot(X, Z, 'b^', label=u"previsão teórica")
plt.legend()
plt.show()


